{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9ea26875",
   "metadata": {},
   "source": [
    "# 模拟退火算法的应用"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "984a071c",
   "metadata": {},
   "source": [
    "## TSP问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "612d87ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import graphviz as gz\n",
    "\n",
    "# 随机生成城市的距离\n",
    "\n",
    "class TSP:\n",
    "\n",
    "    def __init__(self, size):\n",
    "        \n",
    "        self.G_SIZE = size\n",
    "        self.path = None\n",
    "        self.D = np.random.randint(1, 20, (self.G_SIZE, self.G_SIZE))\n",
    "        self.D = self.D - np.diag(self.D.diagonal())\n",
    "        self.D = np.triu(self.D) +  np.triu(self.D).T\n",
    "\n",
    "    def calc_distance(self, arr):\n",
    "        dis = 0;\n",
    "        for i in range(len(arr)-1):\n",
    "            j = i + 1\n",
    "            dis += self.D[arr[i]][arr[j]]\n",
    "        return dis\n",
    "\n",
    "    # 暴力搜索\n",
    "    def dfs(self):\n",
    "        ans = None\n",
    "        path = None\n",
    "        arr = np.array(list(itertools.permutations(np.arange(self.G_SIZE))))\n",
    "        arr = np.hstack([arr,arr[:, 0].reshape(-1, 1)])\n",
    "        # 计算距离\n",
    "        for i in range(len(arr)):\n",
    "            res = self.calc_distance(arr[i])\n",
    "            if ans is not None:\n",
    "                if ans > res:\n",
    "                    ans = res\n",
    "                    path = arr[i]\n",
    "            else:\n",
    "                ans = res\n",
    "                path = arr[i]\n",
    "        return ans, path\n",
    "\n",
    "    # 模拟退火\n",
    "    # 传入当前温度, 降温系数,最小温度,和距离矩阵\n",
    "    def simulatedAnnealing(self, T, r, T_min):\n",
    "        old_dis = None\n",
    "        best_path = None\n",
    "        while(T >= T_min):\n",
    "            # 现在考虑状态转移的方式,出于方便,我们使用numpy的随机排列函数\n",
    "            arr = np.arange(0, self.G_SIZE)\n",
    "            np.random.shuffle(arr)\n",
    "            # 尾部插入首元素成环\n",
    "            arr = np.append(arr, arr[0])\n",
    "            # 计算总距离\n",
    "            dis = self.calc_distance(arr)\n",
    "            if old_dis is not None:\n",
    "                if(old_dis >= dis):\n",
    "                    old_dis = dis\n",
    "                    best_path = arr\n",
    "                elif(old_dis < dis):\n",
    "                    if(np.exp(-(dis - old_dis) / T) > np.random.rand(1)[0]):\n",
    "                        old_dis = dis\n",
    "                        best_path = arr\n",
    "            else:\n",
    "                old_dis = dis\n",
    "                best_path = arr\n",
    "\n",
    "            T *= r\n",
    "            if(T < T_min):\n",
    "                self.path = best_path\n",
    "                return old_dis, best_path\n",
    "\n",
    "    # 绘制图像:\n",
    "\n",
    "    def draw_graph(self, path=None):\n",
    "        if(self.path is not None and path is None):\n",
    "            path = self.path\n",
    "        #生成邻接矩阵记录连接情况\n",
    "\n",
    "        mat = np.zeros((self.G_SIZE, self.G_SIZE))\n",
    "        G = gz.Graph(\"TSP\")\n",
    "        for i in range(len(path)-1):\n",
    "            j = i + 1;\n",
    "            G.edge(str(path[i]), str(path[j]), color = 'red', label=str(self.D[path[i]][path[j]]))\n",
    "            mat[path[i]][path[j]] = 1\n",
    "            mat[path[j]][path[i]] = 1\n",
    "        for i in range(self.G_SIZE):\n",
    "            G.node(str(i))\n",
    "            for j in range(i + 1, self.G_SIZE):\n",
    "                if mat[i][j] == 1:\n",
    "                    continue\n",
    "                G.edge(str(i), str(j), label=str(self.D[i][j]))\n",
    "        return G\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3c71a984",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4.01 ms, sys: 0 ns, total: 4.01 ms\n",
      "Wall time: 7.65 ms\n"
     ]
    }
   ],
   "source": [
    "tsp = TSP(5)\n",
    "%time ans1, path1 = tsp.simulatedAnnealing(10000, 0.96, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "014d293f",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.50.0 (0)\n",
       " -->\n",
       "<!-- Title: TSP Pages: 1 -->\n",
       "<svg width=\"211pt\" height=\"392pt\"\n",
       " viewBox=\"0.00 0.00 211.31 392.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 388)\">\n",
       "<title>TSP</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-388 207.31,-388 207.31,4 -4,4\"/>\n",
       "<!-- 2 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"121.31\" cy=\"-366\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"121.31\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"31.31\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"31.31\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>2&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M102.72,-352.59C93.77,-346.26 83.09,-338.19 74.31,-330 62.92,-319.38 51.5,-305.94 43.29,-295.66\"/>\n",
       "<text text-anchor=\"middle\" x=\"79.31\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"92.31\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"92.31\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;4 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>2&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M118.43,-347.88C112.87,-314.91 100.74,-242.97 95.19,-210.05\"/>\n",
       "<text text-anchor=\"middle\" x=\"118.81\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">17</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"49.31\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"49.31\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.9,-348.34C137.45,-313.78 156.85,-232.63 128.31,-174 115.8,-148.29 88.64,-128.41 69.68,-116.96\"/>\n",
       "<text text-anchor=\"middle\" x=\"147.31\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M42.5,-262.41C53.51,-247.07 70.21,-223.79 81.2,-208.49\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.31\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;3 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>1&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M31.69,-260.65C32.29,-239.96 33.77,-204.36 37.31,-174 39.36,-156.5 43.01,-136.67 45.75,-122.97\"/>\n",
       "<text text-anchor=\"middle\" x=\"46.81\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 4&#45;&#45;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>4&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M84.02,-174.61C76.41,-159.56 65.18,-137.37 57.58,-122.34\"/>\n",
       "<text text-anchor=\"middle\" x=\"78.31\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"96.31\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"96.31\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 3&#45;&#45;0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&#45;0</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M58.37,-87.61C66.75,-72.46 79.12,-50.09 87.44,-35.05\"/>\n",
       "<text text-anchor=\"middle\" x=\"80.31\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>0&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M119.79,-27.58C148.5,-39.77 193.31,-65.04 193.31,-104 193.31,-280 193.31,-280 193.31,-280 193.31,-312.49 162.3,-338.94 140.99,-353.29\"/>\n",
       "<text text-anchor=\"middle\" x=\"198.31\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;1 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>0&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M75.05,-29.36C54.94,-40.48 25.99,-60.23 13.31,-87 -14.69,-146.15 10.9,-227.03 24.31,-261.43\"/>\n",
       "<text text-anchor=\"middle\" x=\"6.31\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;4 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>0&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M95.92,-36.05C95.15,-68.97 93.48,-140.91 92.71,-173.88\"/>\n",
       "<text text-anchor=\"middle\" x=\"99.31\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Graph at 0x7f476030d2b0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tsp.draw_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "id": "e7dc8cf9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.50.0 (0)\n",
       " -->\n",
       "<!-- Title: TSP Pages: 1 -->\n",
       "<svg width=\"216pt\" height=\"392pt\"\n",
       " viewBox=\"0.00 0.00 216.16 392.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 388)\">\n",
       "<title>TSP</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-388 212.16,-388 212.16,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"136.16\" cy=\"-366\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"136.16\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"61.16\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"61.16\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;3 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M123.1,-350.19C109.41,-334.69 88.05,-310.47 74.33,-294.92\"/>\n",
       "<text text-anchor=\"middle\" x=\"111.66\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"42.16\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"42.16\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;1 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>0&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M110.68,-359.95C79.73,-352.29 28.85,-334.48 6.16,-297 -11.45,-267.91 12.83,-228.99 29.27,-207.98\"/>\n",
       "<text text-anchor=\"middle\" x=\"15.66\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">19</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"106.16\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"106.16\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&#45;2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>0&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.19,-348.01C128.76,-301.08 113.58,-170.06 108.14,-123.06\"/>\n",
       "<text text-anchor=\"middle\" x=\"130.66\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 3&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>3&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M57.32,-260.8C54,-245.95 49.23,-224.64 45.93,-209.89\"/>\n",
       "<text text-anchor=\"middle\" x=\"57.16\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"74.16\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"74.16\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&#45;4 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>3&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M45.12,-264.22C31.8,-251.65 13.86,-231.76 6.16,-210 0.82,-194.92 3.31,-189.74 6.16,-174 16.32,-117.95 25.36,-104.78 51.16,-54 54.52,-47.39 58.85,-40.49 62.85,-34.58\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.66\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M53.9,-175.41C65.45,-160.07 82.97,-136.79 94.5,-121.49\"/>\n",
       "<text text-anchor=\"middle\" x=\"82.16\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>1&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M42.39,-173.88C42.95,-153.12 44.85,-117.16 51.16,-87 54.94,-68.95 62.03,-49.04 67.35,-35.46\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.66\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M101.75,-122.87C93.13,-155.81 74.16,-228.31 65.56,-261.19\"/>\n",
       "<text text-anchor=\"middle\" x=\"92.16\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M99.84,-87.21C94.23,-72.31 86.08,-50.65 80.47,-35.76\"/>\n",
       "<text text-anchor=\"middle\" x=\"100.66\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">15</text>\n",
       "</g>\n",
       "<!-- 4&#45;&#45;0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&#45;0</title>\n",
       "<path fill=\"none\" stroke=\"red\" d=\"M99.11,-25.38C132.94,-35.71 189.16,-59.56 189.16,-104 189.16,-280 189.16,-280 189.16,-280 189.16,-308.52 167.41,-335.38 151.78,-351.01\"/>\n",
       "<text text-anchor=\"middle\" x=\"198.66\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Graph at 0x7f50ef584820>"
      ]
     },
     "execution_count": 274,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tsp.draw_graph(path) "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
